import javax.swing.text.html.HTML;
import java.util.HashSet;
import java.util.List;

/**
 * Created by L.jp
 * Description:给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *
 
 * User: 86189
 * Date: 2023-03-21
 * Time: 11:21
 */
class ListNode {
       int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /*ListNode curA=headA;
        ListNode curB=headB;
        while ( curA!=curB ) {
            curA=curA==null ? headB : curA.next;
            curB=curB==null ? headA :curB.next;
        }
        return curA;*/
        
        //哈希表法,先遍历一个链表，再遍历另一个链表查找第一个重复的节点
        HashSet<ListNode> set=new HashSet<>();
        for(ListNode curA=headA;curA != null; curA = curA.next){
            set.add( curA );
        }
        for(ListNode curB=headB;curB != null; curB = curB.next){
            if( set.contains( curB )){
                return curB;
            }
        }
        return null;
        
    }

}
